package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/next-greater-node-in-linked-list/">链表中的下一个更大节点</a>
 * <p>
 * 给定一个长度为 n 的链表 head。<br>
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 <b>严格大于</b> 它的值。
 * 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
 * </p>
 * <pre>
 * 示例 1：
 *      2->1->5
 *      输入：head = [2,1,5]
 *      输出：[5,5,0]
 * 示例 2：
 *      2->7->4->3->5
 *      输入：head = [2,7,4,3,5]
 *      输出：[7,0,5,5,0]
 * </pre>
 * 提示：链表中节点数为 n<br>
 * 1 <= n <= 10^4;
 * 1 <= Node.val <= 10^9
 *
 * @author c2b
 * @since 2023/4/10 15:57
 */
public class LC1019NextLargeNodes_M {

    static class Solution {
        /**
         * 单调栈
         */
        public int[] nextLargerNodes(ListNode head) {
            ListNode currNode = head;
            int length = 0;
            // 计算链表的长度
            while (currNode != null) {
                length++;
                currNode = currNode.next;
            }
            int[] ans = new int[length];
            currNode = head;
            // int[0]-值 int[1]-下标，从0开始
            Deque<int[]> stack = new ArrayDeque<>();
            for (int idx = 0; idx < length; idx++) {
                int currNodeVal = currNode.val;
                while (!stack.isEmpty() && currNodeVal > stack.peekLast()[0]) {
                    int[] ints = stack.pollLast();
                    ans[ints[1]] = currNodeVal;
                }
                stack.offerLast(new int[]{currNodeVal, idx});
                currNode = currNode.next;
            }
            return ans;
        }
    }

    public int[] nextLargerNodes2(ListNode head) {
        ListNode list = head;
        int size = 0;   //链表长度
        List<Integer> valList = new ArrayList<>();  //记录链表中每个节点的值
        while (list != null) {  //计算链表长度
            list = list.next;
            valList.add(list.val);
            size++;
        }
        int[] end = new int[size];  //记录最终答案
        int max = valList.get(size - 1);  //统计当时最大的值是多少，我们是从后往前搜索，所以当前值应该为最后一个arr的值
        int index = size - 1;     //当时最大值的索引是多少
        end[size - 1] = 0;        //最后一个值一定为0
        for (int i = size - 2; i >= 0; i--) {   //从后往前搜索
            if (valList.get(i) >= max) {    //如果当前值大于或等于i后面的最大值，我们就可以更新当前的max以及index，将end[i]也置于0
                index = i;
                max = valList.get(i);
                end[i] = 0;
            } else {              //否则在i和index之间存在一个比arr[i]大的值，直接暴力搜索即可
                for (int j = i + 1; j <= index; j++) {
                    if (valList.get(j) > valList.get(i)) {
                        end[i] = valList.get(j);
                        break;
                    }
                }
            }
        }
        return end;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(7);
        listNode.next.next = new ListNode(5);
        listNode.next.next.next = new ListNode(1);
        listNode.next.next.next.next = new ListNode(9);
        listNode.next.next.next.next.next = new ListNode(2);
        listNode.next.next.next.next.next.next = new ListNode(5);
        listNode.next.next.next.next.next.next.next = new ListNode(1);

        int[] ints = solution.nextLargerNodes(listNode);
        Printer.printArrayInt(ints);
    }
}
